package consistenthash

import (
	"hash/crc32"
	"sort"
	"strconv"
)

//一致性哈希算法解决的问题以及原理
/*
	一致性哈希算法可以使得每个key获取缓存的时候都从指定的节点来获取，减少取缓存的时间，并且可以防止出现缓存雪崩的情况

	缓存雪崩
			缓存在同一时间全部失效，造成瞬间DB请求量大，压力骤增，引起雪崩。常因为缓存服务器宕机，或缓存设置了相同的失效时间

	一致性哈希算法通过将key映射到2^32的空间中，将这个数字首尾相连成环
	1 计算节点/机器（通常使用节点的名称、编号、ip地址）的哈希值，放置在环上
	2 计算key的哈希值，放置在环上，顺时针找到的第一个节点，就是应选取的节点/机器

	一致性哈希算法在新增/删除节点时，只需要重新定位该节点附近的一小部分数据，无需重新定位所有的节点
*/

//Hash maps bytes to uint32
//定义函数类型Hash ，采取依赖注入的方式，
//允许用于替换成自定义的Hash函数，方便测试时替换
type Hash func(data []byte) uint32

//Map constrains all hashed keys
type Map struct {
	hash     Hash           //hash函数
	replicas int            //虚拟节点倍数
	keys     []int          //sorted   哈希环
	hashMap  map[int]string //虚拟节点与真实节点映射表
}

//New creates a Map instance
// 允许自定义虚拟节点背书和Hash函数
func New(replicas int, fn Hash) *Map {
	m := &Map{
		replicas: replicas,
		hash:     fn,
		hashMap:  make(map[int]string),
	}
	if m.hash == nil {
		m.hash = crc32.ChecksumIEEE
	}
	return m
}

//Add adds some keys to the hash
// 实现添加真实节点/机器的Add()方法
func (m *Map) Add(keys ...string) { //允许传入一个或多个真实节点名称
	for _, key := range keys { //循环每个节点
		for i := 0; i < m.replicas; i++ { //循环创建每个虚拟节点
			hash := int(m.hash([]byte(strconv.Itoa(i) + key))) //添加编号的方式+key来区分不同的虚拟节点
			m.keys = append(m.keys, hash)                      //加入到哈希环上
			m.hashMap[hash] = key                              //建立虚拟节点和真实节点映射关系
		}
	}
	sort.Ints(m.keys) //对哈希环进行排序
}

//Get gets the closet item in the hash to the provides key
//实现选择节点的get方法
func (m *Map) Get(key string) string {
	if len(m.keys) == 0 { //如果哈希环长度为0则直接返回空字符串
		return ""
	}
	hash := int(m.hash([]byte(key))) //计算传入的key的hash值
	//Binary search for appropriate replica
	idx := sort.Search(len(m.keys), func(i int) bool { //通过找到哈希环上的第一个匹配的虚拟节点的下标idx
		return m.keys[i] >= hash
	})
	return m.hashMap[m.keys[idx%len(m.keys)]] //通过下标idx找到并返回真实的节点
}
